/**
 * @param {number[]} nums
 */
export var NumArray = function (nums) {
  this.nums = nums
  // 创建一个数组用于存放树状数组
  this.tree = new Array(nums.length + 1).fill(0)
  for (let i = 0; i < nums.length; i++) {
    this.add(i + 1, nums[i]) // 树状数组的索引从1开始
  }
}

/**
 * 在指定的节点上增加数值，其所有父级节点都要增加
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.add = function (index, val) {
  while (index < this.tree.length) {
    this.tree[index] += val
    index += index & -index
  }
}

NumArray.prototype.ask = function (index) {
  let ans = 0
  while (index > 0) {
    ans += this.tree[index]
    index -= index & -index
  }
  return ans
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function (index, val) {
  this.add(index + 1, val - this.nums[index]) // 为当前节点及其所有父节点添加差值
  this.nums[index] = val
}

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
  return this.ask(right + 1) - this.ask(left)
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * obj.update(index,val)
 * var param_2 = obj.sumRange(left,right)
 */
